Maths with Lemon

Walks, trails, paths, Eulerian circuit, Eulerian trail, Hamiltonian cycle, Hamiltonian path

What you have to know:

  • No prior knowledge is required for this section. All concepts are introduced from scratch.

Key Points

  • 1. Watch the video introduction below.

  • 2. Read this presentation for a summary of the definitions and examples.

Kruskal's algorithm

What you have to know:

  • You should understand what vertices, edges and weights represent in a graph.
  • You should know what a cycle is and how to recognise one in a network.
  • No prior algorithm experience is required.

Key Points

  • 1. Watch the video introduction to Kruskal's algorithm.

  • 2. Watch this video on Prim's algorithm as an alternative to Kruskal.

  • 3. Watch this video on Prim's algorithm using an adjacency table.

  • 4. Read these notes on Kruskal's and Prim's algorithms for worked examples.

Chinese postman problem

What you have to know:

  • You must know how to identify odd and even vertices in a graph.
  • You should understand what Eulerian trails and Eulerian circuits are.
  • Basic familiarity with weighted graphs is helpful.

Key Points

  • 1. Watch the video explaining the Chinese postman problem.

Travelling salesman problem

What you have to know:

  • You should understand the difference between a Hamiltonian path and a Hamiltonian cycle.
  • You should be able to interpret a distance or adjacency matrix.
  • You should be comfortable comparing and calculating total route weights.

Key Points

  • 1. Watch the video introduction to the travelling salesman problem.

  • 2. Read this presentation for formal definitions, upper and lower bounds, and examples.

Adjacency matrices

What you have to know:

  • You must know how to multiply matrices.
  • You should understand what each row and column represents in an adjacency matrix.
  • You should know that powers of an adjacency matrix show the number of walks of a given length between vertices.

Key Points

  • 1. Watch the video on adjacency matrices and powers of matrices.

IB Past Paper Problems

Select a topic and unit, then click the button below to get a new problem.

Press the button to start!